/**
 * Created with IntelliJ IDEA
 * Description:
 * User: SEKI TOMOKI
 * Date: 2023-10-06
 * Time: 16:07
 */
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // ListNode curA = headA;
        // ListNode curB = headB;
        // int lenA = 0;
        // int lenB = 0;
        // //求两个链表的长度
        // while(curA != null) {
        //     lenA++;
        //     curA = curA.next;
        // }
        // while(curB != null) {
        //     lenB++;
        //     curB = curB.next;
        // }
        // curA = headA;
        // curB = headB;

        // //求两个链表的差值
        // int longest = lenA > lenB ? lenA : lenB;
        // int shortest = lenA > lenB ? lenB : lenA;
        // int dif = longest - shortest;
        // //最长的链表走差值步
        // if(longest == lenA) {
        //     while(dif != 0) {
        //         curA = curA.next;
        //         dif--;
        //     }
        // }else {
        //     while(dif != 0) {
        //         curB= curB.next;
        //         dif--;
        //     }
        // }
        // //同时走，如果两个指针指向同一个节点，返回这个节点的引用
        // while(shortest != 0) {
        //     if(curA == curB) {
        //         return curA;
        //     }
        //     curA = curA.next;
        //     curB = curB.next;
        //     shortest--;
        // }
        // return null;

        //改进
        ListNode pl = headA;
        ListNode ps = headB;
        int len1 = 0;
        int len2 = 0;
        //求两个链表的长度
        while(pl != null) {
            len1++;
            pl = pl.next;
        }
        while(ps != null) {
            len2++;
            ps = ps.next;
        }
        pl = headA;
        ps = headB;
        //求两个链表的差值
        int len = len1 - len2;
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = len2 - len1;
        }
        //最长的链表走差值步
        while(len != 0) {
            pl = pl.next;
            len--;
        }
        //同时走，如果两个指针指向同一个节点，就结束循环，返回这个节点的引用
        while(pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }
        return pl;
    }
}